/**
 * @Question.Title: 俄罗斯套娃信封问题
 * @Question.No: 354
 * @Author: DQ
 * @Date: 2021-01-24 16:12:56
 * @Description: 
 */
//给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如
//同俄罗斯套娃一样。 
//
// 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。 
//
// 说明: 
//不允许旋转信封。 
//
// 示例: 
//
// 输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
//输出: 3 
//解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
// 
// Related Topics 二分查找 动态规划 
// 👍 263 👎 0

package dq.leetcode.editor.cn;

import java.util.Arrays;
import java.util.Comparator;

public class RussianDollEnvelopes {
    public static void main(String[] args) {
        Solution solution = new RussianDollEnvelopes().new Solution();
        int[][] envelopes = new int[][]{{10,8},{1,12},{10,15},{2,18}};//{{5,4},{6,4},{6,7},{2,3}};
        int res = solution.maxEnvelopes(envelopes);
        System.out.println(res);

       
    }
        //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if(envelopes==null||envelopes.length==0) return 0;
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] e1, int[] e2) {
                if(e1[0]>e2[0]) return 1;
                if(e1[0]==e2[0]) return e1[1]-e2[1]>0?-1:1;
                return -1;
            }
        });
        for (int i = 0; i < envelopes.length; i++) {
            System.out.println(Arrays.toString(envelopes[i]));
        }
//        return s_dp(envelopes);
        return LIS(envelopes);
    }
    //最长递增子序列
    public int LIS(int[][] array){
        int[] piece = new int[array.length];
        piece[0] = array[0][1];
        int len=1;
        for (int i = 1; i < array.length; i++) {
            if(piece[len-1]<array[i][1]) piece[len++] = array[i][1];
            else{
                int index = leftBound(piece, len, array[i][1]);
                piece[index] = array[i][1];
            }
        }
        return len;
    }
    //寻找边界主要是处理 array[mid]==target
    //[0,len]
    public int leftBound(int[] array,int len, int target){
        int left = 0, right = len-1;
        while(left<=right){
            int mid = left + (right-left)/2;
            if(array[mid]>target){
                right = mid-1;
            }else if(array[mid]==target){
                right = mid -1 ;
            }else if(array[mid]<target){
                left = mid+1;
            }
        }

        return left;

    }
    //下列的方法 时间复杂度是 O（n^2）
    public int s_dp(int[][] envelopes) {

        int[] dp = new int[envelopes.length];
        int max = 1;
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }
        for (int i = 0; i < envelopes.length; i++) {
            for (int j = 0; j < i; j++) {
                //i能装下j
                if(great(envelopes[i], envelopes[j])){
                    dp[i] = dp[j]+1>dp[i] ? (dp[j]+1):dp[i];
                    max = dp[i] > max ? dp[i] : max;
                }
            }
        }
        return max;
    }
    private boolean great(int[] e1, int[] e2){

        return e1[0]>e2[0] && e1[1]> e2[1];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}